// https://leetcode.cn/problems/minimum-ascii-delete-sum-for-two-strings/description/

// 算法思路总结：
// 1. 动态规划求解使两个字符串相等的最小删除ASCII和
// 2. 转化为寻找两个字符串的最大公共子序列ASCII和
// 3. 总ASCII和减去两倍公共子序列ASCII和即为最小删除和
// 4. 状态转移：字符相等时累加ASCII值，否则取前状态最大值
// 5. 时间复杂度：O(m×n)，空间复杂度：O(m×n)

#include <iostream>
using namespace std;

#include <vector>
#include <cstring>
#include <algorithm>

class Solution 
{
public:
    int minimumDeleteSum(string s1, string s2) 
    {
        int m = s1.size(), n = s2.size();
        int ret = 0;

        for (char ch : s1)
            ret += (int)ch;
        for (char ch : s2)
            ret += (int)ch;

        vector<vector<int>> dp(m + 1, vector<int>(n + 1, 0));

        s1 = " " + s1;
        s2 = " " + s2;

        for (int i = 1 ; i <= m ; i++)
        {
            for (int j = 1 ; j <= n ; j++)
            {
                if (s1[i] == s2[j])
                    dp[i][j] = dp[i - 1][j - 1] + (int)s1[i];
                dp[i][j] = max({dp[i][j], dp[i - 1][j], dp[i][j - 1]});
            }
        }

        return ret - 2 * dp[m][n];
    }
};
int main()
{
    string s11 = "sea", s12 = "eat";
    string s21 = "delete", s22 = "leet";

    Solution sol;

    cout << sol.minimumDeleteSum(s11, s12) << endl;
    cout << sol.minimumDeleteSum(s21, s22) << endl;

    return 0;
}
